# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        midd = self.middleNode(head)
        right = midd.next
        midd.next = None
        left, right = head, self.reverseList(right)
        while right and left:
            leftNext, rightNext = left.next, right.next
            left.next = right
            right.next = leftNext if leftNext is not None else rightNext
            left = leftNext
            right = rightNext
        
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    def reverseList(self, head):
        pre, curr = None, head
        while curr:
            next = curr.next
            curr.next = pre
            pre = curr
            curr = next
        return pre